
        <html>
			<head>
			     <title>三个白帽条条大路通罗马系列2之二进制题分析 - netwind</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/papers/16380">http://drops.wooyun.org/papers/16380</a></h1>
				
      <p>
        <h1>0x00 前言</h1>

<hr />

<p>该题目是一道算法题，算法涉及二次HASH加密及验证。本人通过分析，认为只有用暴力枚举的方法才能得到认证码。经过长时间跟踪，通过研究加密算法，分析出了通过枚举的方式猜解得到认证码的方法。本文将先对该题进行二进制逆向分析，然后进行算法破解分析。</p>

<h1>0x01 逆向</h1>

<hr />

<p>直接将exe拖入IDA中，然后查找字符串Your code 和Wrong code</p>

<!--more-->

<p><img src="http://static.wooyun.org//drops/20160601/2016060103495182066190.png" alt="" /></p>

<p>找到的每处所在的函数都按F2设置一个断点：</p>

<p><img src="http://static.wooyun.org//drops/20160601/2016060103495386691248.png" alt="" /></p>

<p>选择local win32 debugger，然后点击开始按钮进行调试：</p>

<p><img src="http://static.wooyun.org//drops/20160601/2016060103495586348327.png" alt="" /></p>

<p>这时候程序中断在我们设置的断点处：</p>

<p><img src="http://static.wooyun.org//drops/20160601/2016060103495788915423.png" alt="" /></p>

<p>上图中，如果界面显示的是汇编代码，直接按一下F5就切换到了伪C代码里了。</p>

<p>上面的代码具体是干什么的，我们暂时不去关心，这时按F9让程序继续执行，然后输入认证码，随便输入一串字符就好，输长一点，回车之后到达了我们之前下断的wrong code这里，IDA反编译的伪C代码如下：</p>

<pre><code>#!c
int __cdecl sub_431970(int a1, int a2)
{
   memset(&amp;v4, 0xCCu, 0x108u);   //这里memset是我肉眼识别出函数功能后，做的标记，
  v6 = strlen(secret[0]);//   secret[0]   一个内存中固定的字符串
  v5 = a2;
  for ( i = 0; i &lt; 0x10; i += 4 )
  {
    v7 = 0;
    for ( j = i; j &lt; i + 4; ++j )
    {
      for ( k = 0; ; ++k )
      {
        v2 = strlen(secret[0]);
        if ( k &gt;= v2 )
          break;
        if ( secret[0][k] == *(_BYTE *)(j + a1) )  //a1 由b@@<a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="3c486f7c7e64">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>@<a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="1e555e7a70">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>@@X转换得到
        {
          v7 &lt;&lt;= 6;
          v7 += k;
          break;
        }
      }
    }
    *(_BYTE *)v5 = v7 &gt;&gt; 16;
    *(_BYTE *)(v5 + 1) = BYTE1(v7);
    *(_BYTE *)(v5 + 2) = v7;
    v5 += 3;
  }
  return sub_42FDC0();
}
</code></pre>

<p>通过阅读上面的代码，以及跟踪分析，首先发现字符串a1是把我们输入的认证码依次替换掉<code>b@@<a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="81f5d2c1c3d9">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>@<a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="1b505b7f75">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>@@X</code>中的<code>@</code>得到的。另外字符串secret[0]是固定的值为：<code>R9Ly6NoJvsIPnWhETYtHe4Sdl+MbGujaZpk102wKCr7/ODg5zXAFqQfxBicV3m8U</code></p>

<p>通过查看内存值，便一目了然：</p>

<p><img src="http://static.wooyun.org//drops/20160601/2016060103495867693519.png" alt="" /></p>

<p><img src="http://static.wooyun.org//drops/20160601/2016060103500029999618.png" alt="" /></p>

<p>通过分析算法发现他的HASH加密算法如下：</p>

<p>把a1字符串每4个一组，如果字符a1[i]是字符串secret[0]里的字符，那么</p>

<pre><code>#!c
V7=0
Hash= v7&lt;&lt;6+k //k是a1[i]在字符串secret[0]里的下标。
</code></pre>

<p>如果a1[i+1]依然满足条件</p>

<p>那么<code>hash= hash&lt;&lt;6+k；</code>依次进行，经过4个字符后 V7从0开始 再hash后面四个字符。</p>

<p>把最终得到的4组hash值以16进制形式存入内存中，每组HASH得到一个3字节的数据，4组完成后共得到12字节数据。</p>

<p>这里随便输入的认证码，本次HASH运算完，得到的12字节数据如下：</p>

<p><img src="http://static.wooyun.org//drops/20160601/2016060103500277335718.png" alt="" /></p>

<p>然后第一次HASH结束。</p>

<p>在函数尾部下断点，F9 一次，再F8后来到了 程序最开始的函数中，也就是第一次我们断下的函数里：</p>

<p><img src="http://static.wooyun.org//drops/20160601/2016060103500443487814.png" alt="" /></p>

<p>继续按F8，进入了下面的函数：</p>

<pre><code>#!c
int __cdecl sub_431E10(int a1)
{
  memset(&amp;v2, 0xCCu, 0x114u);
  v9 = a1;
  v8 = strlen(a1);
  strlen(secret[0]) = strlen(secret[0]);
  if ( v8 != 12 )                           这里检查我们上面得到的HASH后的内容是否是12字节
  {
    sub_43019E("Wrong code!\n");
    sub_4302C0(1u);
  }
  for ( i = 0; i &lt; v8; ++i )
  {
    v5 = 0;
    for ( j = 0; j &lt; strlen(secret[0]); ++j )
    {
      if ( secret[0][j] == *(_BYTE *)(i + v9) )   //这里检查上面HASH后的每一个字节对应的字符是否在
//字符串secret[0]里
      {
        v5 = 1;
        break;
      }
    }
    if ( !v5 )
    {
      sub_43019E("Wrong code!\n");    //如果不是 就挂了。
      sub_4302C0(1u);
    }
  }
  v3 = malloc(16);
  memset(v3, 0, 16);
  sub_430045(v9, v3);
  sub_42F3F2(v3);
  return sub_42FDC0();
}
</code></pre>

<p>如果上面认证全部通过，按F9后，会进入HASH加密的函数：</p>

<p>这个时候需要进行加密的就是上面得到的第一次HASH加密后的12字节数据。</p>

<p>对这12字节加密，每4个一组，共3组，每组得到3字节数据，这样第二次HASH后就得到了9字节的数据。按F9后到达这里：</p>

<pre><code>#!c
int __cdecl sub_431CA0(int a1)
{
   memset(&amp;v2, 0xCCu, 0xF0u);
  v6 = a1;
  v5 = strlen(a1);
  if ( v5 != 9 )   //首先判断第二次HASH后的字节长度是否为9，不是就错了。
  {
    sub_43019E("Wrong code!\n");
    sub_4302C0(1u);
  }
  for ( i = 0; i &lt; v5; ++i )
  {
    if ( (signed int)*(_BYTE *)(i + v6) &lt; 48 || (signed int)*(_BYTE *)(i + v6) &gt; 57 )  //检查第二次HASH后的//每个字节是否都为数字 //字符
    {
      sub_43019E("Wrong code!\n");
      sub_4302C0(1u);
    }
  }
  for ( i = 0; i &lt; v5; ++i )
  {
    for ( j = i + 1; j &lt; v5; ++j )
    {
      if ( *(_BYTE *)(i + v6) == *(_BYTE *)(j + v6) )  //检查第二次HASH后的每个字节是否彼此重复。
      {
        sub_43019E("Wrong code!\n");
        sub_4302C0(1u);
      }
    }
  }
  sub_42F1D1(v6);                                 //如果上面都通过了 ，就到达了胜利的彼岸了！
  return sub_42FDC0();
}
</code></pre>

<p>以上就是整个二进制算法的逆向过程，这里我们搞清楚了他的加密算法，下面就是尝试破解认证码了。</p>

<h1>0x02 算法破解</h1>

<hr />

<p>针对第一部分HASH算法，我计划是从<code>R9Ly6NoJvsIPnWhETYtHe4Sdl+MbGujaZpk102wKCr7/ODg5zXAFqQfxBicV3m8U</code>里任意选取两个（根据需要也可能是1个）字符分别填充到<code>b@@t <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="5f0c1f1d07">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script> @<a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="53181337">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script> n@@X</code>，并分组进行HASH加密，再验证HASH结果是否满足条件，如果满足条件，那么就保存一下选取的字符以及HASH后的密文。</p>

<p>具体算法如下：</p>

<pre><code>#!c
char m2[17]="b@@<a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="f387a0b3b1ab">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>@<a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="a8e3e8ccc6">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>@@X",*p,*q;
    int in1=0,in2=0,in3=0,in4=0;
    q=m2;
    get(q,0,1,2);   //分组取hash  参数分别为字符串 序号  m2里需要填充的字符坐标
    q+=4;
    get(q,1,1,0);
    q+=4;
    get(q,2,0,2);
    q+=4;
    get(q,3,1,2);    //共4组，到这里infos就得到了所有满足第一次HASH结果的可能的值
</code></pre>

<p>针对第二次HASH加密，我们把get()函数获得的所有满足条件的密文字符串进行组合，然后对每组字符串再次尝试hash加密，把得到的结果进行检查是否每个字符都是0-9内并且互不重复，把满足条件的结果记录下来。</p>

<p>最后完整破解认证码的代码如下：</p>

<pre><code>#!c
#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;windows.h&gt;
char m1[70]="R9Ly6NoJvsIPnWhETYtHe4Sdl+MbGujaZpk102wKCr7/ODg5zXAFqQfxBicV3m8U";
char sz[11]="0123456789";
struct info
{
    char *hash;  //存放第一次hash后的值
    char *mw;    //存放hash前明文
};
info infos[4][1000];
long hash(char *s) 
{   
    int j=0,v7=0,k=0;
    v7 = 0;
    for ( j = 0; j &lt;  4; ++j )
    {
        for ( k = 0; ; ++k )
        {
            if ( k &gt;=  strlen(m1))
                break;
            if ( m1[k] == s[j] )
            {
                v7 &lt;&lt;= 6;
                v7 += k;
                break;
            }
        }
    }
    return v7;
}
int check(char a,char *s)  //检查字符a是否在字符串s里
{   
    int i=0;
    for (i=0;i&lt;strlen(s);i++)
    {
        if (s[i]==a)
        {
            return 1;
        }
    }
    return 0;
}
int check2(char *s)  //第二次hash 每次hash后检查一下 是否在0-9间，同时检查一下是否有重复数字
{
    int v7=hash(s);
    char *v5;
    v5=(char *)malloc(4);
    v5[0] = char(v7 &gt;&gt; 16);
    v5[1] = char(v7 &gt;&gt; 8);
    v5[2] = char(v7);
    v5[3]='\0';
    if ( !check(v5[0],sz) || !check(v5[1],sz) || !check(v5[2],sz) )
    {   
        return 0;
    }
    else if(v5[0]==v5[1]||v5[0]==v5[2]||v5[1]==v5[2])
    {
        return 0;   
    }
    else
        return 1;
}
void get(char *s,int index,int in1,int in2)  //暴力枚举 获得满足第一次hash结果的 hash密文 和明文
{
    char *p,*q,char ms[3];
    char *v5;
    int i0=0,i=0,j=0,v7=0,k=0,num=0;
    p=q=s;
    for (i0=0;i0&lt;64;i0++)
    {
        p[in1]=m1[i0];
        for ( i = 0; i &lt; 64; i ++ )
        {
            if (in2!=0)
            {
                p[in2]=m1[i];
            }
            else
                i=65;           
            v7=hash(p);
            v5=(char *)malloc(4);
            v5[0] = char(v7 &gt;&gt; 16);
            v5[1] = char(v7 &gt;&gt; 8);
            v5[2] = char(v7);
            v5[3]='\0';
            if ( check(v5[0],m1) &amp;&amp; check(v5[1],m1) &amp;&amp; check(v5[2],m1) )
            {
                infos[index][num].hash=(char *)malloc(4);
                strcpy(infos[index][num].hash,v5);

                ms[0]=p[in1];
                if (in2==0)
                {
                    ms[1]='\0';
                }
                else
                {
                    ms[1]=p[in2];
                    ms[2]='\0';
                }
                infos[index][num].mw=(char *)malloc(3);
                strcpy(infos[index][num].mw,ms);
                num++;
                delete v5;
            }

        }
        if (i&lt;64)
        {
            break;
        }
    }
}
void main()
{
    char m2[17]="b@@<a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="04705744465c">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>@<a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="024942666c">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>@@X",*p,*q;
    int in1=0,in2=0,in3=0,in4=0;
    q=m2;
    get(q,0,1,2);   //分段hash  参数分别为字符串 序号  m2里需要填充的字符坐标
    q+=4;
    get(q,1,1,0);
    q+=4;
    get(q,2,0,2);
    q+=4;
    get(q,3,1,2);    //到这里infos就得到了所有满足第一次HASH结果的可能的值
    char temp1[15],temp2[15],temp3[15],temp4[15];
    for(in1=0;;in1++)    //暴力枚举 所有组合，查找满足第二次条件的值
    {
        if (!infos[0][in1].hash)
        {
            break;
        }
        strcpy(temp1,infos[0][in1].hash);
        for (in2=0;;in2++)
        {
            strcpy(temp2,temp1);
            if (!infos[1][in2].hash)
            {
                break;
            }
            strcat(temp2,infos[1][in2].hash);
            p=temp2;
            if (!check2(p))
            {
                continue;
            } 
            for (in3=0;;in3++)
            {

                strcpy(temp3,temp2);
                if (!infos[2][in3].hash)
                {
                    break;
                }
                strcat(temp3,infos[2][in3].hash);
                p=temp3+4;
                if (!check2(p))
                {
                    continue;
                }
                for (in4=0;;in4++)
                {
                    strcpy(temp4,temp3);
                    if (!infos[3][in4].hash)
                    {
                        break;
                    }
                    strcat(temp4,infos[3][in4].hash);
                    p=temp4+8;
                    if (!p||!check2(p))
                    {
                        continue;
                    }
                    else
                    {
                        p=temp4;
                        char result[10];
                        result[0]='\0';
                        for (int i=0;i&lt;3;i++)
                        {
                            int v7=hash(p);
                            char *v5=(char *)malloc(4);
                           v5[0] = char(v7 &gt;&gt; 16);
                           v5[1] = char(v7 &gt;&gt; 8);
                           v5[2] = char(v7);
                           v5[3]='\0'; 
                           strcat(result,v5);
                           p+=4;
                        }
                        for (i=0;i&lt;strlen(result);i++)
                        {
                            char tt=result[i];
                            result[i]='a';
                            if (check(tt,result))
                            {
                                break;
                            }
                            result[i]=tt;
                        }
                        if (i==strlen(result))
                        {
                            puts("got it!!!");
                            printf("%s%s%s%s\n",infos[0][in1].mw,infos[1][in2].mw,infos[2][in3].mw,infos[3][in4].mw);
                        }

                    }   

                }

            }
        }

    }
}
</code></pre>

<h1>0x03 验证</h1>

<hr />

<p>破解代码运行后结果如下：</p>

<p><img src="http://static.wooyun.org//drops/20160601/2016060103500624950915.png" alt="" /></p>

<p>得到了两个结果：</p>

<p>分别输入两个结果，显示如下：</p>

<p><img src="http://static.wooyun.org//drops/20160601/20160601035008312301014.png" alt="" /></p>

<p>第一个结果，输入后没任何反应，也不提示错误。第二个输入后成功得到flag。</p>

<p>分析认为这个加密算法有2个解，但是最终能解密FLAG的只有第二个才可以。</p>

<h1>0x04 总结</h1>

<hr />

<p>本题主要是通过两次HASH运算 并分别进行验证的方式加密；两次都可以根据已知限制条件，分别采用暴力枚举的方式进行暴力破解。虽然破解代码量有点大，但是破解速度并没有收到影响，执行破解代码后能马上得到结果！</p>

<p>文中有分析不当或不周全的地方，希望大家批评指正！</p>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          